Knowledge of network topology is useful for network diagnostics, performance tuning and monitoring. One method of obtaining information about network topology is to use traceroute. However, traceroute creates a list of IP addresses that correspond to the interfaces of the routers used from source to destination. These routers have multiple interfaces and there is, a priori, no way to tell that two IP addresses are interfaces on the same router.
To illustrate the difference between a topology based on network interfaces and a topology based on devices we can compare FIG. 1 and FIG. 2. In FIG. 1, each node represents a network device while in FIG. 2, each node is a network interface. Network engineers often want to know about the topology of FIG. 1; however, FIG. 2 is of little use to the network engineer precisely because it does not incorporate the classification of interfaces by device.
Going from the topology of FIG. 2 to the more useful topology of FIG. 1 requires that the IP addresses observed in the traceroute results be classified according to the router to which they belong. The classification is known as IP de-aliasing. Errors in resolving such a conflict can affect the usefulness of the topology. The impact of such errors with respect to various essential network characteristics has been studied in works such as M. H. Gunes and K. Sarac “Importance of IP Alias Resolution in Sampling Internet Topologies,” Proc. IEEE Global Internet, 2006. In addition, various approaches have been proposed to perform IP alias resolution. One of the earliest methods was introduced by J. Pansiot and D. Grad in “On Routes and Multicast Trees in the Internet,” in ACM Computer Communication Review, volume 28, pages 41-50, January 1998. This method relied on the fact that when a router generates a packet for an ICMP port unreachable message, the message generally appears to come from the emitting interface rather than from the interface to which the original packet was sent. Extensions to this approach have been used in the Mercator project (R. Govindan and H. Tangmunarunkit, “Heuristics for Internet Map Discovery,” in IEEE INFOCOM 2000, pages 1371-1380, Tel Aviv, Israel, March 2000) and in the Rocketfuel tool (N. Spring, R. Mahajan, and D. Wetherall, “Measuring ISP Topologies with Rocketfuel,” in Proceedings of IEEE/ACM Transactions on Networking, volume 12, February 2004). Quite a different solution was suggested by M. H. Gunes and K. Sarac in “Analytical IP Alias Resolution,” in IEEE International Conference on Communication, General Symposium, June 2006, to exploit common IP address assignment schemes. This latter method has the advantage of requiring much less probing than what the J. Pansiot paper described.
Standard methods for IP de-aliasing include DNS, SNMP and TELNET. Each of these methods, however, has shortcomings that render them difficult to apply consistently and automatically on a large network. SNMP and TELNET, for example, require the knowledge of device passwords. Even with the proper authentication, which might be possible to obtain on a private network, information uncovered by these methods is often entered by humans and thus potentially out-of-date or inaccurate. Another obstacle to using SNMP effectively is that there is no standard SNMP variable that uniquely identifies a device.
Alternative methods that do not suffer these shortcomings rely on data collected by endpoints distributed throughout a network. The idea behind these approaches is that an endpoint is a vantage from which a quantitative view of the network topology, made up of devices (and their associated IP addresses), can be obtained. This approach reveals device identities by considering how an endpoint interacts with the devices. Typical interactions include responses such as: 1) round trip times; 2) IP time stamps; 3) IP packet IDs; 4) IP Record Routes. If two IP addresses belong to the same device, then measurements taken at the same time from an endpoint to these two IP addresses should be similar in round trip time, identical in time stamps, sequential in packet ID values, and finally, IP Recorded Routes to the two IP address should be identical. Unfortunately, except for the first test, the rest of the tests all require strong assumptions about the network. For response 2, it must be the case that the network time protocol (NTP) is not running since it interferes with IP time stamps. For response 3 devices need to use sequentially increasing packet IDs on a per device basis, rather than on a per interface basis as many devices do. Response 4 is based on the assumption that network paths have less than 9 hops, because IP Record Route is limited to 9 hops.
It would therefore be desirable to provide a method for IP address de-aliasing that is useful on private networks, that does not require strong assumptions about the underlying network, and that can address the de-aliasing problem and provide an accurate representation of the topology of a network.